class Solution {
public:
    pair<int, int> dp[15][2];
    bool flag[15][2];
    int countDigitOne(int n) {
        return dfs(to_string(n), 0, 0).second;
    }
    pair<int, int> dfs(string s, int pos, int free)
    {
        int n1 = 0;
        int n2 = 0;
        if (pos >= s.size()) return pair<int, int>(1, 0);
        if (flag[pos][free]) return dp[pos][free];
        for (char i = '0'; i <= '9'; i++)
        {
            if (!free && i > s[pos]) break;
            if (free)
            {
                pair<int, int> temp = dfs(s, pos + 1, 1);
                n1 += temp.first * (i == '1') + temp.second;
                n2 += temp.first;
            }
            else
            {
                pair<int, int> temp = dfs(s, pos + 1, i < s[pos]);
                n1 += temp.first * (i == '1') + temp.second;
                n2 += temp.first;
            }
        }
        flag[pos][free] = 1;
        return dp[pos][free] = pair<int, int>(n2, n1);
    }
};